package danran.dfs;

import java.util.Arrays;

/**
 * @Classname LongestIncreasingPath
 * @Description TODO
 * @Date 2021/9/22 10:30
 * @Created by ASUS
 */
public class LongestIncreasingPath {
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int maxPath = 0;
    boolean[][] visited;
    int[][] pathLength;

    public int longestIncreasingPath(int[][] matrix) {
        visited = new boolean[matrix.length][matrix[0].length];
        pathLength = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                pathLength[i][j] = -1;
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                maxPath = Math.max(dfs(matrix, i, j), maxPath);
            }
        }
        Arrays.stream(pathLength).forEach(a -> System.out.println(Arrays.toString(a)));
        return maxPath;
    }

    private int dfs(int[][] matrix, int x, int y) {
        if (pathLength[x][y] != -1) return pathLength[x][y];
        int ans = 1;
        visited[x][y] = true;
        for (int[] dir : dirs) {
            int dx = x + dir[0], dy = y + dir[1];
            if (dx < 0 || dx == matrix.length || dy < 0 || dy == matrix[0].length) continue;
            if (!visited[dx][dy]) {
                if (matrix[dx][dy] > matrix[x][y]) {
                    if (pathLength[dx][dy] != -1) ans = Math.max(1 + pathLength[dx][dy], ans);
                    else ans = Math.max(1 + dfs(matrix, dx, dy), ans);
                }

            }
        }
        visited[x][y] = false;
        pathLength[x][y] = Math.max(ans, pathLength[x][y]);
        return ans;
    }

    public static void main(String[] args) {
        System.out.println("[[0,1,2,3,4,5,6,7,8,9],[19,18,17,16,15,14,13,12,11,10],[20,21,22,23,24,25,26,27,28,29],[39,38,37,36,35,34,33,32,31,30],[40,41,42,43,44,45,46,47,48,49],[59,58,57,56,55,54,53,52,51,50],[60,61,62,63,64,65,66,67,68,69],[79,78,77,76,75,74,73,72,71,70],[80,81,82,83,84,85,86,87,88,89],[99,98,97,96,95,94,93,92,91,90],[100,101,102,103,104,105,106,107,108,109],[119,118,117,116,115,114,113,112,111,110],[120,121,122,123,124,125,126,127,128,129],[139,138,137,136,135,134,133,132,131,130],[0,0,0,0,0,0,0,0,0,0]]".replace('[', '{').replace(']', '}'));
        int[][] matrix = {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, {19, 18, 17, 16, 15, 14, 13, 12, 11, 10}, {20, 21, 22, 23, 24, 25, 26, 27, 28, 29}, {39, 38, 37, 36, 35, 34, 33, 32, 31, 30}, {40, 41, 42, 43, 44, 45, 46, 47, 48, 49}, {59, 58, 57, 56, 55, 54, 53, 52, 51, 50}, {60, 61, 62, 63, 64, 65, 66, 67, 68, 69}, {79, 78, 77, 76, 75, 74, 73, 72, 71, 70}, {80, 81, 82, 83, 84, 85, 86, 87, 88, 89}, {99, 98, 97, 96, 95, 94, 93, 92, 91, 90}, {100, 101, 102, 103, 104, 105, 106, 107, 108, 109}, {119, 118, 117, 116, 115, 114, 113, 112, 111, 110}, {120, 121, 122, 123, 124, 125, 126, 127, 128, 129}, {139, 138, 137, 136, 135, 134, 133, 132, 131, 130}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
        Arrays.stream(matrix).forEach(a -> System.out.println(Arrays.toString(a)));

        System.out.println(new LongestIncreasingPath().longestIncreasingPath(matrix));
    }
}
